The present invention relates to a compression system and method, and more particularly, the present invention relates to a compression method that can be used with geographic data used by a navigation application program that provides navigating features and functions to an end-user.
Computer-based navigation application programs are available that provide end-users (such as drivers of vehicles in which the navigation systems are installed) with various navigating functions and features. For example, some navigation application programs are able to determine an optimum route to travel by roads between locations in a geographic region. Using input from an end-user, and optionally from equipment that can determine one""s physical location (such as a GPS system), a navigation application program can examine various routes between two locations to determine an optimum route to travel from a starting location to a destination location in a geographic region. The navigation application program may then provide the end-user with information about the optimum route in the form of instructions that identify the maneuvers required to be taken by the end-user to travel from the starting location to the destination location. If the navigation system is located in an automobile, the instructions may take the form of audio instructions that are provided along the way as the end-user is traveling the route. Some navigation application programs are able to show detailed maps on computer displays outlining routes to destinations, the types of maneuvers to be taken at various locations along the routes, locations of certain types of features, and so on.
In order to provide these and other navigating functions, the navigation application program uses one or more detailed databases that include data which represent physical features in a geographic region. The detailed database may include data representing the roads and intersections in a geographic region and also may include information relating to the represented roads and intersections in a geographic region, such as turn restrictions at intersections, speed limits along the roads, street names of the various roads, address ranges along the various roads, and so on.
One difficulty in providing geographic data for use by a navigation application program relates to the efficient utilization of the available computer resources of the navigation system on which the navigation application program is run. Computer-based navigation application programs are provided on various platforms including some with relatively limited computer resources. For example, navigation systems may be located in vehicles or may be hand-held. These types of navigation systems may have relatively limited computer resources, such as limited memory and relatively slow I/O. In order to provide a high a level of functionality in such systems, it is required that the available computer resources be used efficiently.
The limited resources of some navigation systems can affect the ability of these types of navigation systems to provide desired navigation functions, especially when using a relatively large geographic database that includes a relatively high level of detail. Handling the large amounts of data included in a geographic database may adversely affect the performance of navigation systems with limited resources.
Another consideration related to the use of geographic data by navigation systems is that given the relatively large size of the geographic database necessary to provide a desired level of functionality to the end-user, all the data records for an entire geographic region cannot be loaded into the memory of the navigation system at the same time. This is especially true for navigation system platforms with limited resources, such as systems installed in vehicles or hand-held systems. Due to the limited memory resources of these navigation systems, it is necessary to load geographic data as needed from a storage medium, such as a CD-ROM disk, into the memory of the navigation system for use by the navigation application program. Unfortunately, in these types of systems, I/O access from a storage medium may be relatively slow. Thus, the relatively limited memory resources of some types of navigation systems, combined with relatively slow I/O, can limit performance thereby resulting in slow response. Aside from being undesirable, slow response in a navigation system may render the system useless for its intended purpose in certain circumstances. For example, if the navigation system is installed in a vehicle, the driver may require information from the navigation system about a desired route in a matter of seconds in order to utilize the information while driving. If the navigation system requires more than several seconds to calculate a route, the driver may have moved beyond the point at which the routing information provided by the navigation system is relevant. Therefore, it is important that navigation systems operate efficiently in order to provide navigating information relatively quickly.
Navigation application programs may also be run on computer platforms that have in general greater memory resources and faster I/O, such as personal computers or networks. Although these systems may have more and faster resources, the considerations related to the efficient use of geographic data still apply, but on a larger scale. With these types of systems, even greater functionality can be provided if the limitations imposed by memory size and I/O are minimized.
To improve the performance of navigation systems generally and in particular to compensate for the limitations of some navigation system platforms with limited hardware resources, techniques have been devised or implemented to improve navigation system performance by organizing, structuring, or arranging the geographic database or the data in the geographic database in particular ways. Because a navigation system uses geographic data in certain known and expected ways to perform known functions, the geographic data can be organized, structured, or arranged in ways that facilitate their use in these known ways by the navigation system.
One of the techniques that can be used to facilitate the use of geographic data by navigation systems is to organize at least some of the geographic data spatially. When geographic data are organized spatially, geographic features that are close together physically in the geographic region are represented by data records that are, in general, close together in the database and/or on the medium. This kind of organization may minimize the amount of searching in the geographic database when performing some navigation functions.
Another technique that can be used to facilitate access by an application in a navigation system is to organize at least some of the geographic database into groupings (or parcels). When geographic data are organized into parcels, the plurality of data records that together comprise the geographic database are separated into separate groupings (or parcels). The selection of data records to be included in each parcel is based upon a likelihood that all the data records needed to perform a particular navigation function are included in relatively few parcels. For example, parcels may be used to organize some or all of the geographic data spatially. Using parcelization to organize geographic data spatially, geographic features that are located close together physically in the geographic region are represented by data records that are included in the same parcel. Various criteria may be used as a basis for organizing geographic data into parcels, including non-spatial factors such as by administrative area, alphabetical by name, and so on.
Another technique that can be implemented in a geographic database to enhance operation of the navigation system is to minimize consideration of minor or secondary roads during calculation of a route. One way to suppress consideration of minor or secondary roads is to organize some or all of the geographic data into layers using rankings assigned to roads in a geographic region. The rankings can be related to a functional classification of the roads. Major roads upon which travel is generally faster are assigned higher rankings and minor roads upon which travel is generally slower are assigned lower rankings. Using these rankings, data records that represent higher ranked roads can be stored in separate layers in the geographic database. The navigation application program uses the higher layers when possible. Since the higher layers omit slower secondary roads, these generally slower roads are not considered when the higher layers are used to calculate the route, thereby minimizing the possible road segments that need to be investigated. This kind of database arrangement may facilitate the route calculation navigation function, thereby providing improved navigation system performance.
In addition to spatial organization, parcelization, and layering, there are other techniques that can be implemented in a geographic database that can enhance the performance of a navigation application in the navigation system that uses the geographic database. Some or all of the above techniques can be used together in a geographic database to enhance operation of a navigation application that uses the geographic database.
One factor that affects the way that the geographic database is used by a navigation system relates to the size of the coverage area of the geographic database. The coverage area of a geographic database refers to the size of the geographic region represented by the data in the geographic database. A coverage area may include an entire metropolitan area, such as New York and its suburbs, Chicago and its suburbs, or Los Angeles and its suburbs. A coverage area may also include an entire country, such as Germany. In general, it is preferable to make the coverage area as large as possible.
Factors that may affect the size of the coverage area of a geographic database include the type of media upon which the geographic database is stored and the level of detail of the geographic database. In order to provide the navigation features desired by navigation system end-users, a geographic database includes a relatively large amount of data with a correspondingly high level of detail. Various kinds of media can be used for storing a geographic database in a navigation system. These different kinds of media include, for example, CD-ROM disks, PCMCIA cards, hard disks, DVD disks, and so on. Each of these different kinds of media has advantages and disadvantages. Regardless of the kind of media used, it would be desired to store as much data on the media as possible, thereby providing as large a coverage area as possible, or as much detail as possible, or a maximum combination of coverage area and detail. Thus, the geographic data should be stored efficiently on the medium.
There are conventional data compression techniques that increase the amount of data that can be stored on a medium. Some conventional data compression techniques have the disadvantage of requiring substantial additional processing to decompress the data from a compressed form in which they are stored on the medium. This additional processing may adversely affect performance of some navigation systems. In addition, some conventional data compression techniques involve rearranging portions of the data or substituting portions of the original collection of data with other data. Such data compression techniques may be incompatible with the techniques, described above, that enhance certain navigation functions. If such conventional data compression techniques are not entirely incompatible with the navigation enhancing techniques, described above, they may nonetheless offset the advantages associated with the navigation enhancing techniques.
Accordingly, it is one objective to provide a means to store geographic data efficiently on a medium. It is another objective to provide one or more data compression techniques in a geographic database that is organized in a manner that facilitates its use by a navigation application program. It is another objective to provide a data compression technique that can be used for various kinds of data, and geographic data in particular.
To address the above concerns, according to one aspect of the present invention, a data compression system and method are provided. The data compression system and method can be used to compress various kinds of data, and in particular, can be used to compress geographic data stored on a physical data storage medium. The data compression method comprises searching in a preceding portion of an input stream of data characters from a first position for a sequence of a plurality of data characters that matches a sequence of a plurality of data characters at the first position. Upon finding a matching sequence of a plurality of data characters, the sequence of a plurality of data characters for which a matching sequence of a plurality of data characters was found in the preceding portion of the input stream is replaced with a reference to the matching sequence of a plurality of data characters in the preceding portion of the input stream. The reference comprises a backwards offset from the first position to the position in the preceding portion of the input stream at which the matching sequence of a plurality of data characters is located and a size of the matching sequence.
According to further aspects, the backward offsets, the data that indicate the sizes of the matching sequences, the data that indicate the lengths of non-substitution code characters, and the literal characters themselves can be Huffman encoded. In an application of the data compression method to geographic data that has been organized to facilitate access and use by a navigation application program, the one or more Huffman trees for decoding the Huffman codes are stored in a separate portion of the database from portions that include the data records that have been compressed using the Huffman encoding.
According to a further aspect of the disclosed subject matter, a decompression method and program are provided. The decompression method reverses the compression process. Starting from one end of a compressed data stream and advancing through the compressed data stream to the other end, as substitution codes are encountered, the substitution codes are replaced with substrings which are located in previous portions of the data stream. Each substitution code includes a backwards offset and an indication of the substitution substring length. When each substitution code is encountered during the step of advancing through the compressed data stream during decompression, a substring of the indicated substitution substring length and located at the position in the previous portion of the data stream indicated by the backwards offset is inserted to the portion of the data stream.